#include <vector>
#include <map>
#include <iostream>
#include <queue>
#include <functional>
#include <queue>
#include "UnionFindSet.hpp"
using namespace std;

namespace matrix
{
    template <class V, class W, W W_MAX = INT32_MAX, bool Direction = false>
    class Graph
    {
        vector<V> _vertexs;        // 顶点集合
        map<V, size_t> _indexmap;  // 顶点映射下标
        vector<vector<W>> _matrix; // 邻接矩阵

    public:
        Graph() = default;

        Graph(const V *vertexs, size_t n)
        {
            _vertexs.reserve(n);
            for (size_t i = 0; i < n; ++i)
            {
                _vertexs.push_back(vertexs[i]);
                _indexmap.insert(make_pair(vertexs[i], i));
            }

            _matrix.resize(n);
            for (vector<W> &e : _matrix)
            {
                e.resize(n, W_MAX);
            }
        }

        size_t GetIndex(const V &vertex)
        {
            auto it = _indexmap.find(vertex);
            if (it != _indexmap.end())
            {
                return it->second;
            }
            else
            {
                throw invalid_argument("不存在的顶点");
                return UINT32_MAX;
            }
        }

        bool AddEdge(const V &src, const V &des, const W &w)
        {
            size_t s = GetIndex(src);
            size_t d = GetIndex(des);

            if (s == UINT32_MAX || d == UINT32_MAX)
                return false;

            _AddEdge(s, d, w);
            return true;
        }

        void _AddEdge(size_t s, size_t d, const W &w)
        {
            _matrix[s][d] = w;
            if (!Direction)
                _matrix[d][s] = w;
        }

        void Print()
        {
            size_t n = _vertexs.size();
            // 打印顶点和下标的映射关系
            for (size_t i = 0; i < n; ++i)
            {
                cout << "[" << i << "]";
                cout << " --> ";
                cout << _vertexs[i] << endl;
            }
            cout << endl;

            // 打印矩阵
            cout << "  ";
            for (size_t k = 0; k < n; ++k)
                cout << k << " "; // 打印列号
            cout << endl;
            for (size_t i = 0; i < n; ++i)
            {
                cout << i << " "; // 打印行号
                for (size_t j = 0; j < n; ++j)
                {
                    if (_matrix[i][j] == W_MAX)
                        cout << "∞ ";
                    else
                        cout << _matrix[i][j] << " ";
                }
                cout << endl;
            }
            cout << endl;

            // 打印所有的边
            for (size_t i = 0; i < n; ++i)
            {
                for (size_t j = 0; j < i; ++j)
                {
                    if (_matrix[i][j] != W_MAX)
                    {
                        cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl;
                    }
                }
            }
        }

        void BFS(const V &start)
        {
            queue<int> que;                               // 队列
            vector<bool> visited(_vertexs.size(), false); // 标记数组

            // 将起点入队，标记
            int starti = GetIndex(start);
            que.push(starti);
            visited[starti] = true;
            int d = 1; // 遍历层数

            while (!que.empty())
            {
                while (d--)
                {
                    int front = que.front();
                    que.pop();
                    cout << "[" << front << "]" << _vertexs[front] << " ";
                    for (int i = 0; i < _vertexs.size(); ++i)
                    {
                        if (_matrix[front][i] != W_MAX && !visited[i])
                        {
                            que.push(i);
                            visited[i] = true;
                        }
                    }
                }
                d = que.size();
                cout << endl;
            }
        }

        void DFS(const V &start)
        {
            int starti = GetIndex(start);
            vector<bool> visited(_vertexs.size(), false);
            _DFS(starti, visited);
        }

        void _DFS(int index, vector<bool> &visited)
        {
            cout << "[" << index << "]" << _vertexs[index] << endl;
            visited[index] = true;
            for (int i = 0; i < _vertexs.size(); ++i)
            {
                if (_matrix[index][i] != W_MAX && !visited[i])
                {
                    _DFS(i, visited);
                }
            }
        }

        struct Edge
        {
            size_t _srci;
            size_t _dsti;
            W _w;

            Edge(size_t srci, size_t dsti, W w)
                : _srci(srci),
                  _dsti(dsti),
                  _w(w)
            {
            }

            bool operator>(const Edge &e) const
            {
                return _w > e._w;
            }
        };

        W Kruskal(Graph &mintree)
        {
            size_t n = _vertexs.size();

            // 初始化最小生成树
            mintree._vertexs = _vertexs;
            mintree._indexmap = _indexmap;
            mintree._matrix.resize(n);
            for (vector<W> &e : mintree._matrix)
            {
                e.resize(n, W_MAX);
            }

            // 将所有边添加到优先级队列
            priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
            for (size_t i = 0; i < n; ++i)
            {
                for (size_t j = 0; j < i; ++j)
                {
                    if (_matrix[i][j] != W_MAX)
                    {
                        minque.emplace(i, j, _matrix[i][j]);
                    }
                }
            }

            // 为最小生成树添加边
            UnionFindSet ufs(n);  // 构造一个并查集，用于判断添加的边是否能构成回路
            size_t edgeCount = 0; // 边数统计
            W totalW = W();       // 最小生成树所有边的权值总和
            while (edgeCount < n - 1 && !minque.empty())
            {
                Edge top = minque.top();
                minque.pop();

                // 如果不在一个集合当中，表示添加该边后不会构成回路
                if (!ufs.InSet(top._srci, top._dsti))
                {
                    mintree._AddEdge(top._srci, top._dsti, top._w);
                    ufs.Union(top._srci, top._dsti);
                    ++edgeCount;
                    totalW += top._w;
                    // cout << _vertexs[top._srci] << "->" << _vertexs[top._dsti] << ":" << top._w << endl;
                }
                // else
                // {
                //     cout << "构成回路：" << _vertexs[top._srci] << "->" << _vertexs[top._dsti] << ":" << top._w << endl;
                // }
            }

            if (edgeCount == n - 1)
            {
                return totalW;
            }
            else
            {
                return W(); // 如果不是连通图，没有最小生成树，返回默认值
            }
        }

        W Prim(Graph &mintree, const V &start)
        {
            size_t n = _vertexs.size();
            size_t starti = GetIndex(start);

            // 初始化最小生成树
            mintree._vertexs = _vertexs;
            mintree._indexmap = _indexmap;
            mintree._matrix.resize(n);
            for (vector<W> &e : mintree._matrix)
            {
                e.resize(n, W_MAX);
            }

            // 将与起点相连的边添加到优先级队列
            priority_queue<Edge, vector<Edge>, greater<Edge>> que;
            for (size_t i = 0; i < n; ++i)
            {
                if (_matrix[starti][i] != W_MAX)
                {
                    que.emplace(starti, i, _matrix[starti][i]);
                }
            }

            vector<bool> inset(_vertexs.size(), false); // 标记集合中的顶点，防止成环
            inset[starti] = true;
            size_t vertexCount = 1; // 统计集合中顶点的个数
            W totalW = W();         // 最小生成树所有边的权值总和

            // 为最小生成树添加边
            while (vertexCount < n && !que.empty())
            {
                Edge top = que.top();
                que.pop();

                // 判断添加的边是否成环
                if (!inset[top._dsti])
                {
                    mintree._AddEdge(top._srci, top._dsti, top._w);
                    ++vertexCount;
                    totalW += top._w;
                    inset[top._dsti] = true;
                    // cout << _vertexs[top._srci] << "->" << _vertexs[top._dsti] << ":" << top._w << endl;

                    // 将与新顶点相连的边添加到优先级队列
                    for (size_t i = 0; i < n; ++i)
                    {
                        if (_matrix[top._dsti][i] != W_MAX && !inset[i])
                        {
                            que.emplace(top._dsti, i, _matrix[top._dsti][i]);
                        }
                    }
                }
                // else
                // {
                //     cout << "构成回路：" << _vertexs[top._srci] << "->" << _vertexs[top._dsti] << ":" << top._w << endl;
                // }
            }

            if(vertexCount == n)
            {
                return totalW;
            }
            else
            {
                return W(); // 如果不是连通图，没有最小生成树，返回默认值
            }
        }
    };
};

namespace link_table
{
    template <class W>
    struct EdgeNode
    {
        size_t _dsti;    // 边的终点
        W _w;            // 边的权值
        EdgeNode *_next; // 节点后继指针

        EdgeNode(size_t dsti, W w)
            : _dsti(dsti),
              _w(w),
              _next(nullptr)
        {
        }
    };

    template <class V, class W, bool Direction = false>
    class Graph
    {
        typedef EdgeNode<W> Edge;
        vector<V> _vertexs;       // 顶点集合
        map<V, size_t> _indexmap; // 顶点映射下标
        vector<Edge *> _table;    // 邻接表

    public:
        Graph() = default;

        Graph(const V *vertexs, size_t n)
        {
            _vertexs.reserve(n);
            for (size_t i = 0; i < n; ++i)
            {
                _vertexs.push_back(vertexs[i]);
                _indexmap.insert(make_pair(vertexs[i], i));
            }

            _table.resize(n, nullptr);
        }

        size_t GetIndex(const V &vertex)
        {
            auto it = _indexmap.find(vertex);
            if (it != _indexmap.end())
            {
                return it->second;
            }
            else
            {
                throw invalid_argument("不存在的顶点");
                return UINT32_MAX;
            }
        }

        bool AddEdge(const V &src, const V &des, const W &w)
        {
            size_t s = GetIndex(src);
            size_t d = GetIndex(des);

            Edge *eg = new Edge(d, w);
            eg->_next = _table[s];
            _table[s] = eg;

            if (!Direction)
            {
                Edge *eg = new Edge(s, w);
                eg->_next = _table[d];
                _table[d] = eg;
            }
        }

        void Print()
        {
            // 打印顶点和下标的映射关系
            for (size_t i = 0; i < _vertexs.size(); ++i)
            {
                cout << "[" << i << "]";
                cout << " --> ";
                cout << _vertexs[i] << endl;
            }
            cout << endl;

            // 打印邻接表
            for (size_t i = 0; i < _table.size(); ++i)
            {
                cout << "[" << i << "]" << _vertexs[i] << "->";
                Edge *cur = _table[i];
                while (cur != nullptr)
                {
                    cout << "[" << cur->_dsti << "]" << _vertexs[cur->_dsti];
                    cout << ":" << cur->_w << "->";
                    cur = cur->_next;
                }
                cout << "nullptr" << endl;
            }
        }
    };
};
